{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Verify Preorder Serialization of a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #string #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #字符串 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isValidSerialization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证二叉树的前序序列化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>序列化二叉树的一种方法是使用 <strong>前序遍历 </strong>。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 <code>#</code>。</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/12/pre-tree.jpg\" /></p>\n",
    "\n",
    "<p>例如，上面的二叉树可以被序列化为字符串 <code>\"9,3,4,#,#,1,#,#,2,#,6,#,#\"</code>，其中 <code>#</code> 代表一个空节点。</p>\n",
    "\n",
    "<p>给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。</p>\n",
    "\n",
    "<p><strong>保证</strong> 每个以逗号分隔的字符或为一个整数或为一个表示 <code>null</code> 指针的 <code>'#'</code> 。</p>\n",
    "\n",
    "<p>你可以认为输入格式总是有效的</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如它永远不会包含两个连续的逗号，比如&nbsp;<code>\"1,,3\"</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意：</strong>不允许重建树。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>preorder = <code>\"9,3,4,#,#,1,#,#,2,#,6,#,#\"</code>\n",
    "<strong>输出: </strong><code>true</code></pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>preorder = <code>\"1,#\"</code>\n",
    "<strong>输出: </strong><code>false</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>preorder = <code>\"9,#,#,1\"</code>\n",
    "<strong>输出: </strong><code>false</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= preorder.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>preorder</code>&nbsp;由以逗号&nbsp;<code>“，”</code> 分隔的 <code>[0,100]</code> 范围内的整数和 <code>“#”</code> 组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [verify-preorder-serialization-of-a-binary-tree](https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [verify-preorder-serialization-of-a-binary-tree](https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"9,3,4,#,#,1,#,#,2,#,6,#,#\"', '\"1,#\"', '\"9,#,#,1\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        lists = list(preorder.split(\",\"))\n",
    "\n",
    "        # 初始时有一个槽位（对应根节点）\n",
    "        slots = 1\n",
    "        for char in lists:\n",
    "            if slots == 0:\n",
    "                return False\n",
    "            if char == \"#\":\n",
    "                slots -= 1\n",
    "            else:\n",
    "                slots += 1\n",
    "        \n",
    "        # 遍历完后槽位数量应该正好为0\n",
    "        return slots == 0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        nodes = preorder.split(\",\")\n",
    "        diff = 1\n",
    "        for node in nodes:\n",
    "            diff -= 1\n",
    "            if diff<0:\n",
    "                return False\n",
    "            if node!=\"#\":\n",
    "                diff+=2\n",
    "        return diff==0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        nodes = preorder.split(',')\n",
    "        diff = 1\n",
    "        for node in nodes:\n",
    "            diff -= 1\n",
    "            if diff < 0:\n",
    "                return False\n",
    "            if node != '#':\n",
    "                diff += 2\n",
    "        return diff == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack=[]\n",
    "        for node in preorder.split(\",\"):\n",
    "            stack.append(node)\n",
    "            while len(stack)>=3 and stack[-1]==stack[-2]=='#' and stack[-3] !='#':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append(\"#\")\n",
    "        return len(stack)==1 and stack.pop()=='#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidSerialization(self, preorder):\n",
    "        nodes = preorder.split(',')\n",
    "        diff = 1\n",
    "        for node in nodes:\n",
    "            diff -= 1\n",
    "            if diff < 0:\n",
    "                return False\n",
    "            if node != '#':\n",
    "                diff += 2\n",
    "        return diff == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        for c in preorder.split(','):\n",
    "            stack.append(c)\n",
    "            if c =='#':\n",
    "                while len(stack) >= 2 and stack[-1] == stack[-2] == '#':\n",
    "                    stack.pop()\n",
    "                    stack.pop()\n",
    "                    if len(stack) == 0 or stack[-1] == '#':\n",
    "                        return False\n",
    "                    stack.pop()\n",
    "                    stack.append('#')\n",
    "        # print(stack)\n",
    "        return len(stack) == 0 or (len(stack) == 1 and stack[0]== '#')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        slot = 1\n",
    "        for i in range(len(preorder)):\n",
    "            if preorder[i] in \"0123456789\":\n",
    "                if i == len(preorder) - 1 or preorder[i + 1] == \",\":\n",
    "                    slot += 1\n",
    "            elif preorder[i] == \"#\":\n",
    "                slot -= 1\n",
    "            if slot <= 0 and i != len(preorder) - 1:\n",
    "                return False\n",
    "        if not slot:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 2. count, SPACE COMPLEXITY - O(1)\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        order_len = len(preorder)\n",
    "        idx = 0\n",
    "        slock = 1\n",
    "        while idx < order_len:\n",
    "            if slock == 0:\n",
    "                return False\n",
    "            \n",
    "            if preorder[idx] == ',':\n",
    "                idx += 1\n",
    "            elif preorder[idx] == '#':\n",
    "                slock -= 1\n",
    "                idx += 1\n",
    "            else:\n",
    "                while idx < order_len and preorder[idx] != ',':\n",
    "                    idx += 1\n",
    "                slock += 1\n",
    "        return slock == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        node_list = preorder.split(\",\")\n",
    "        diff = 1\n",
    "        for node in node_list:\n",
    "            diff -= 1\n",
    "            if diff < 0:\n",
    "                return False\n",
    "            if node != \"#\":\n",
    "                diff += 2\n",
    "        return diff == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        ans = 1\n",
    "        arr = preorder.split(',')\n",
    "\n",
    "        leng = len(arr)\n",
    "        \n",
    "        for item in range(0, leng):\n",
    "            if arr[item] == '#':\n",
    "                ans -= 1\n",
    "            else:\n",
    "                ans += 1\n",
    "            if ans <= 0 and item != leng - 1:\n",
    "                return False\n",
    "        return ans == 0\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        # stack = [1] # 根节点的槽\n",
    "        # for s in preorder.split(','):\n",
    "        #     if stack:\n",
    "        #         stack[-1] -= 1 # 填槽\n",
    "        #         if stack[-1] == 0:\n",
    "        #             stack.pop()\n",
    "        #     else:\n",
    "        #         return False\n",
    "        #     if s != '#':\n",
    "        #         stack.append(2) # 加两个槽（左右孩子的）\n",
    "        # return len(stack) == 0\n",
    "\n",
    "        slots = 1 # 根节点的槽\n",
    "        for s in preorder.split(','):\n",
    "            if slots > 0:\n",
    "                slots -= 1 # 填槽\n",
    "            else:\n",
    "                return False\n",
    "            if s != '#':\n",
    "                slots += 2 # 加两个槽（左右孩子的）\n",
    "        return slots == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\r\n",
    "        preorder = preorder.split(\",\")\r\n",
    "        if preorder[-1] != \"#\":\r\n",
    "            return False\r\n",
    "        a = b = 0\r\n",
    "        for item in preorder[:-1]:\r\n",
    "            if item == \"#\":\r\n",
    "                a += 1\r\n",
    "            else:\r\n",
    "                b += 1\r\n",
    "            if a>b:\r\n",
    "                return False\r\n",
    "        return a==b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        diff = 1\n",
    "        for node in preorder.split(','):\n",
    "            diff -= 1\n",
    "            if diff < 0:\n",
    "                return False\n",
    "            if node != '#':\n",
    "                diff += 2\n",
    "        return diff == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        for i in preorder.split(','):\n",
    "            stack.append(i)\n",
    "            while len(stack) >= 3 and stack[-1] == '#' and stack[-2] == '#' and stack[-3] != '#':\n",
    "                stack.pop(),stack.pop(),stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'\n",
    "         \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack=[]\n",
    "        for node in preorder.split(','):\n",
    "            stack.append(node)\n",
    "            while len(stack)>=3 and stack[-1]==stack[-2]=='#' and stack[-3]!='#':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack)==1 and stack[-1]=='#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        pre_list=preorder.split(',')\n",
    "        last_len=len(pre_list)\n",
    "        while last_len>2:  \n",
    "            i=len(pre_list)-1\n",
    "            while i>=2:\n",
    "                if pre_list[i]=='#' and pre_list[i-1]=='#' and pre_list[i-2]!='#':\n",
    "                    pre_list[i-2:i+1]='#'\n",
    "                    i-=2\n",
    "                else:\n",
    "                    i-=1\n",
    "            if len(pre_list)==last_len:\n",
    "                return False\n",
    "            last_len=len(pre_list)\n",
    "        if len(pre_list)==1 and pre_list[0]=='#':\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def isValidSerialization(self, preorder: str) -> bool:\n",
    "    #     node_list = preorder.split(',')\n",
    "    #     n = len(node_list)\n",
    "    #     if n == 0:\n",
    "    #         return True\n",
    "    #     if n == 1:\n",
    "    #         return node_list[0] == '#'\n",
    "    #     def traverse(i):\n",
    "    #         if node_list[i] == '#':\n",
    "    #             return i\n",
    "    #         second_child = i+2\n",
    "    #         if i+1 >= n:\n",
    "    #             return 0\n",
    "    #         elif node_list[i+1] != \"#\":\n",
    "    #             second_child = traverse(i+1) + 1\n",
    "\n",
    "    #         if second_child >= n or not second_child:\n",
    "    #             return 0\n",
    "    #         elif node_list[second_child] == '#':\n",
    "    #             return second_child\n",
    "    #         else:\n",
    "    #             return traverse(second_child)\n",
    "    #     return traverse(0) == n-1\n",
    "\n",
    "    # def isValidSerialization(self, preorder):\n",
    "    #     stack = []\n",
    "    #     for node in preorder.split(','):\n",
    "    #         stack.append(node)\n",
    "    #         while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#':\n",
    "    #             stack.pop(), stack.pop(), stack.pop()\n",
    "    #             stack.append('#')\n",
    "    #     return len(stack) == 1 and stack.pop() == '#'\n",
    "\n",
    "    def isValidSerialization(self, preorder):\n",
    "        nodes = preorder.split(',')\n",
    "        diff = 1\n",
    "        for node in nodes:\n",
    "            diff -= 1\n",
    "            if diff < 0:\n",
    "                return False\n",
    "            if node != '#':\n",
    "                diff += 2\n",
    "        return diff == 0\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        pos = 1\n",
    "        for node in preorder.split(\",\"):\n",
    "            if pos == 0:\n",
    "                return False\n",
    "            pos += -1 if node == '#' else 1\n",
    "        return pos == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        node_list = preorder.split(',')\n",
    "        i = 1\n",
    "        while 0 <= i < len(node_list) - 1:\n",
    "            if node_list[i] == node_list[i + 1] == '#' and node_list[i-1] != '#':\n",
    "                node_list[i - 1:i + 2] = '#'\n",
    "                i -= 2\n",
    "            else:\n",
    "                i += 1\n",
    "        return node_list == ['#']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = [1] # 根节点的槽\n",
    "        for s in preorder.split(','):\n",
    "            if stack:\n",
    "                stack[-1] -= 1 # 填槽\n",
    "                if stack[-1] == 0:\n",
    "                    stack.pop()\n",
    "            else:\n",
    "                return False\n",
    "            if s != '#':\n",
    "                stack.append(2) # 加两个槽（左右孩子的）\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 前序遍历的验证策略：当加入一个非空节点时，可认为创造了2-1=1个槽位；加入一个空节点时，填补了一个槽位\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        if preorder=='#':# 空树\n",
    "            return True\n",
    "        preorder_list = preorder.split(',')\n",
    "        n = len(preorder_list)\n",
    "        stk = list()\n",
    "        if preorder[0].isdigit():# 第一个节点非空，创造两个槽位\n",
    "            stk.append(2)\n",
    "        for i in range(1,n):\n",
    "            if len(stk)==0:# 栈为空，但还有节点，说明不是一棵树\n",
    "                return False\n",
    "            top_num = stk.pop()\n",
    "            top_num -= 1# 不管是什么节点，都占用了一个槽位\n",
    "            if top_num > 0:\n",
    "                stk.append(top_num)\n",
    "            elif top_num <0:# 栈顶元素小于0时，说明引入了过量空节点，导致树不成树\n",
    "                return False\n",
    "            if preorder_list[i].isdigit():# 非空节点，增加两个槽位\n",
    "                stk.append(2)\n",
    "        return len(stk)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        t = preorder.split(\",\")\n",
    "        n = len(t)\n",
    "\n",
    "        st = [1]\n",
    "        for o in t:\n",
    "            if not st:\n",
    "                return False\n",
    "            x = st.pop()\n",
    "            if x - 1 > 0:\n",
    "                st.append(x - 1)\n",
    "            if o != \"#\":\n",
    "                st.append(2)\n",
    "        return not st\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        st = [1]\n",
    "        preorder = preorder.split(',')\n",
    "        for char in preorder:\n",
    "            if char == \"#\":\n",
    "                if st and st[-1]>0:\n",
    "                    st[-1] -=1\n",
    "                    if st[-1] == 0:\n",
    "                        st.pop()\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if not st:\n",
    "                    return False\n",
    "                else:\n",
    "                    st[-1] -=1\n",
    "                    if st[-1] == 0:\n",
    "                        st.pop()\n",
    "                    st.append(2)\n",
    "        if not st:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = 1\n",
    "        isnum = 0\n",
    "        for x in preorder:\n",
    "            if x == ',':\n",
    "                isnum = 0\n",
    "                continue\n",
    "            if isnum==1:\n",
    "                continue\n",
    "            if stack == 0:\n",
    "                return False\n",
    "            if x == '#':\n",
    "                stack-=1\n",
    "            else:\n",
    "                isnum = 1\n",
    "                stack+=1\n",
    "        return stack==0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        st = []\n",
    "        for p in preorder.split(','):\n",
    "            st.append(p)\n",
    "            while (len(st)) >= 3 and st[-1] == '#' and st[-2] == '#' and st[-3] != '#':\n",
    "                st.pop(), st.pop(), st.pop()\n",
    "                st.append('#')\n",
    "        return len(st) == 1 and st[-1] == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        if not preorder:\n",
    "            return True\n",
    "        if len(preorder) == 1:\n",
    "            if preorder[0] != '#':\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        if preorder[0] == '#':\n",
    "            return False\n",
    "        queue = []\n",
    "        preorder = preorder.split(',')\n",
    "        queue.append(2)\n",
    "        for i in range(1, len(preorder)):\n",
    "            if not queue:\n",
    "                 return False\n",
    "            a = queue.pop()\n",
    "            a -= 1\n",
    "            if a > 0:\n",
    "                queue.append(a)\n",
    "            if preorder[i] != '#':\n",
    "                queue.append(2)\n",
    "        if queue:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        # chs=preorder.split(',')\n",
    "        # def dfs(left,right):\n",
    "        #     if right==left:\n",
    "        #         if chs[left]=='#':return True\n",
    "        #         else:return False\n",
    "        #     elif right-left==1:return False\n",
    "        #     elif right-left==2:\n",
    "        #         if chs[left]!='#' and chs[left+1]==chs[right]=='#':return True\n",
    "        #         return False\n",
    "        #     else:\n",
    "        #         if chs[left]=='#':return False\n",
    "        #         for i in range(left+1,right):\n",
    "        #             if dfs(left+1,i) and dfs(i+1,right):return True\n",
    "        #         return False\n",
    "        # return dfs(0,len(chs)-1)\n",
    "\n",
    "        def lt331_2(s):\n",
    "            dq=deque(s.split(','))\n",
    "            temp=deque([])\n",
    "            while len(dq)>1:\n",
    "                shortened=False\n",
    "                for i in range(len(dq)):\n",
    "                    temp.append(dq.popleft())\n",
    "                    if len(temp)==3:\n",
    "                        if temp[0]!='#' and temp[1]==temp[2]=='#':\n",
    "                            dq.append('#')\n",
    "                            if not shortened:shortened=True\n",
    "                            temp=deque([])\n",
    "                        else:\n",
    "                            dq.append(temp.popleft())\n",
    "                while temp:dq.append(temp.popleft())\n",
    "                if not shortened:return False\n",
    "            return dq[0]=='#'\n",
    "        return lt331_2(preorder)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidSerialization(self, preorder):\n",
    "        stack = []\n",
    "        for node in preorder.split(','):\n",
    "            stack.append(node)\n",
    "            while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#':\n",
    "                stack.pop(), stack.pop(), stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        for i in preorder.split(','):\n",
    "            stack.append(i)\n",
    "            while len(stack)>2 and stack[-1]=='#' and stack[-2]=='#' and stack[-3]!='#':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append('#')\n",
    "                \n",
    "            \n",
    "        if len(stack)==1 and stack[0]==\"#\":\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        for node in preorder.split(','):\n",
    "            stack.append(node)\n",
    "            while len(stack) >= 3 and stack[-1] == '#' and stack[-2] == '#' and stack[-3] != '#':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        for p in preorder.split(','):\n",
    "            stack.append(p)\n",
    "            while len(stack) > 2 and stack[-1] == stack[-2] == '#' and stack[-3]!='#':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                # stack.pop()\n",
    "                # stack.append('#')\n",
    "                stack[-1] = '#'\n",
    "        return len(stack) == 1 and stack[-1] == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        s = preorder.split(\",\")\n",
    "        diff = 1\n",
    "        for x in s:\n",
    "            diff -= 1\n",
    "            if diff < 0:\n",
    "                return False\n",
    "            if x != \"#\":\n",
    "                diff += 2\n",
    "        return diff == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        st = []\n",
    "        if preorder == \"#\":return True\n",
    "        first = True\n",
    "        preorder = preorder.split(',')\n",
    "        for char in preorder:\n",
    "            print(char,st)\n",
    "            if char == \"#\":\n",
    "                if st and st[-1]>0:\n",
    "                    st[-1] -=1\n",
    "                    if st[-1] == 0:\n",
    "                        st.pop()\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if not st:\n",
    "                    if first:\n",
    "                        st.append(2)\n",
    "                        first = False\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    st[-1] -=1\n",
    "                    if st[-1] == 0:\n",
    "                        st.pop()\n",
    "                    st.append(2)\n",
    "        \n",
    "        if not st:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        #序列化必须是前序遍历\n",
    "        stack=[]\n",
    "        for node in preorder.split(','):#每一个节点用“,”隔开  \n",
    "            stack.append(node)\n",
    "            while len(stack)>2 and stack[-1]==stack[-2]=='#' and stack[-3]!='#':\n",
    "            #栈的长度是3，栈底的是叶子节点，栈顶前两个都为#\n",
    "                 stack.pop()#弹出栈顶第一个#\n",
    "                 stack.pop()#弹出栈顶第二个#\n",
    "                 stack.pop()#弹出栈顶的叶子节点\n",
    "                 #叶子节点变为#\n",
    "                 stack.append('#')\n",
    "        return len(stack)==1 and stack.pop()=='#'\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        degree = 1\n",
    "        for node in preorder.split(','):\n",
    "            if degree == 0:\n",
    "                return False\n",
    "            if node == '#':\n",
    "                degree -= 1\n",
    "            else:\n",
    "                degree += 1\n",
    "        return degree == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        nodes = preorder.split(',')\n",
    "        diff = 1\n",
    "        for node in nodes:\n",
    "            diff -= 1\n",
    "            if diff < 0:\n",
    "                return False\n",
    "            if node != '#':\n",
    "                diff += 2\n",
    "        return diff == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidSerialization(self, preorder):\n",
    "        stack = []\n",
    "        for node in preorder.split(','):\n",
    "            stack.append(node)\n",
    "            while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#':\n",
    "                stack.pop(), stack.pop(), stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = list()\n",
    "        for i in preorder.split(','):\n",
    "            stack.append(i)\n",
    "            # 每个元素都入栈，只要最靠近栈顶的三个元素为[num, #, #]的形式，就弹出，然后补入#。最终栈内只剩下#才能返回True，其它情况都返回False\n",
    "            while len(stack) > 2 and stack[-1] == '#' and stack[-2] == '#' and stack[-3].isdigit():\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append('#')\n",
    "        return True if stack == ['#'] else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        for s in preorder.split(','):\n",
    "            stack.append(s)\n",
    "            while len(stack) > 2 and stack[-1] == stack[-2] == '#' and stack[-3] != '#':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        patt = re.compile('\\d+,#,#')\n",
    "        old = preorder\n",
    "        while (preorder:=re.sub(patt,'#',preorder)) != old:\n",
    "            old = preorder\n",
    "        return old == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        diff = 1\n",
    "        for node in preorder.split(','):\n",
    "            diff -= 1\n",
    "            if diff < 0:\n",
    "                return False\n",
    "            if node != '#':\n",
    "                diff += 2\n",
    "        return diff == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        for p in preorder.split(','):\n",
    "            stack.append(p)\n",
    "            while len(stack) > 2 and stack[-1] == stack[-2] == '#' and stack[-3]!='#':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack[-1] == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        nodes = preorder.split(\",\")\n",
    "\n",
    "        def helper(nodes):\n",
    "            new = []\n",
    "            i = 0\n",
    "            found = False\n",
    "            while i < len(nodes):\n",
    "                if i + 2 < len(nodes) and nodes[i] != \"#\" and nodes[i + 1] == \"#\" and nodes[i + 2] == \"#\":\n",
    "                    new += \"#\"\n",
    "                    found = True\n",
    "                    i += 3\n",
    "                else:\n",
    "                    new.append(nodes[i])\n",
    "                    i += 1\n",
    "            \n",
    "            if not found:\n",
    "                return new\n",
    "\n",
    "            return helper(new)\n",
    "        \n",
    "        ans = helper(nodes)\n",
    "        return len(ans) == 1 and ans[0] == \"#\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = 1\n",
    "        isnum = 0\n",
    "        for x in preorder:\n",
    "            if x == ',':\n",
    "                isnum = 0\n",
    "                continue\n",
    "            if isnum==1:\n",
    "                continue\n",
    "            if stack == 0:\n",
    "                return False\n",
    "            if x == '#':\n",
    "                stack-=1\n",
    "            else:\n",
    "                isnum = 1\n",
    "                stack+=1\n",
    "        return stack==0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        nodes = preorder.split(',')\n",
    "        diff = 1\n",
    "        for node in nodes:\n",
    "            diff -= 1\n",
    "            if diff < 0:\n",
    "                return False\n",
    "            if node != '#':\n",
    "                diff += 2\n",
    "        return diff == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidSerialization(self, preorder):\n",
    "        stack = []\n",
    "        for node in preorder.split(','):\n",
    "            stack.append(node)\n",
    "            while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#': ### 找到一个椰子树节点了\n",
    "                stack.pop(), stack.pop(), stack.pop() ### 全都pop出去\n",
    "                stack.append('#') ### 加入一个标记\n",
    "        return len(stack) == 1 and stack.pop() == '#'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack=[]\n",
    "        for node in preorder.split(\",\"):\n",
    "            stack.append(node)\n",
    "            while len(stack)>=3 and stack[-1]==stack[-2]=='#' and stack[-3]!='#':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack)==1 and stack[-1]=='#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        tmp = preorder.split(',')\n",
    "        stack = 1\n",
    "        for x in tmp:\n",
    "            if stack == 0:\n",
    "                return False\n",
    "            if x == '#':\n",
    "                stack-=1\n",
    "            else:\n",
    "                stack+=1\n",
    "        return stack==0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        if preorder == '':\n",
    "            return False\n",
    "        # 使用栈\n",
    "        n = len(preorder)\n",
    "        i = 0\n",
    "        stack = [1]\n",
    "        while i < n:\n",
    "            if not stack: \n",
    "                return False\n",
    "            if preorder[i] == ',':\n",
    "                i += 1\n",
    "            elif preorder[i] == '#':\n",
    "                stack[-1] -= 1\n",
    "                if stack[-1] == 0: \n",
    "                    stack.pop()\n",
    "                i += 1\n",
    "            else:\n",
    "                while i < n and preorder[i] != ',': \n",
    "                    i += 1\n",
    "                stack[-1] -= 1\n",
    "                if stack[-1] == 0: \n",
    "                    stack.pop()\n",
    "                stack.append(2)\n",
    "        return len(stack) == 0\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        # 开始的时候有一个槽位可以放\n",
    "        degree = 1\n",
    "        for node in preorder.split(\",\"):\n",
    "            # ==0的时候就代表后面的挂不上去了，不合法\n",
    "            if degree == 0:\n",
    "                return False\n",
    "            if node == \"#\":\n",
    "                degree -= 1\n",
    "            else:\n",
    "                degree += 1\n",
    "        return degree == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidSerialization(self, preorder):\n",
    "        stack = []\n",
    "        for node in preorder.split(','):\n",
    "            stack.append(node)\n",
    "            while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#':\n",
    "                stack.pop(), stack.pop(), stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidSerialization(self, preorder): ### 一个‘#’代表一个空！\n",
    "\n",
    "        stack=[]\n",
    "        for root in preorder.split(\",\"):\n",
    "            stack.append(root)\n",
    "            while len(stack)>=3 and stack[-2]==\"#\" and stack[-1]==\"#\" and stack[-3] != '#': ## 这里必须管-3\n",
    "            ### 测试中有多个*项链的情况\n",
    "                stack.pop(),stack.pop(),stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'\n",
    "\n",
    "        # stack=[]\n",
    "        # for root in preorder.split(','):\n",
    "        #     stack.append(root)\n",
    "        #     print(stack)\n",
    "        #     while len(stack)>=3 and stack[-1]==stack[-2]=='#' and stack[-3] != '#': ### 这里绝对不能用if，\n",
    "        #     ## 比如消掉4，1 以后，应该再次消掉新生成的3\n",
    "        #         stack.pop(),stack.pop(),stack.pop()\n",
    "        #         stack.append('#')\n",
    "        # return len(stack) == 1 and stack.pop() == '#'\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # stack = []\n",
    "        # for node in preorder.split(','):\n",
    "        #     stack.append(node)\n",
    "        #     while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#': ### 找到一个椰子树节点了\n",
    "        #         stack.pop(), stack.pop(), stack.pop() ### 全都pop出去\n",
    "        #         stack.append('#') ### 加入一个标记\n",
    "        # return len(stack) == 1 and stack.pop() == '#'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        if preorder=='#':\n",
    "            return True\n",
    "\n",
    "        # 栈模拟\n",
    "        stack=[]\n",
    "        preorder_list=preorder.split(',')\n",
    "        count=0\n",
    "        for num in preorder_list:\n",
    "            if stack==[]:\n",
    "                count+=1\n",
    "            if num!='#':\n",
    "                stack.append([num,0])\n",
    "            else:\n",
    "                # 遇到了井号\n",
    "                if stack==[]:\n",
    "                    return False\n",
    "                while stack!=[] and stack[-1][1]==1:\n",
    "                    stack.pop()\n",
    "                if stack!=[]:\n",
    "                    stack[-1][1]=1\n",
    "        return stack==[] and count==1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        preorderList = preorder.split(',')\n",
    "        i = 0\n",
    "        while len(preorderList) >= 0 and 0<=i<len(preorderList):\n",
    "            if i+2<len(preorderList) and preorderList[i] != '#' and preorderList[i+1] == preorderList[i+2] == '#':\n",
    "                preorderList[i:i+3] = ['#']\n",
    "                i -= 1\n",
    "                if i>=0 and preorderList[i] == '#':\n",
    "                    i -= 1\n",
    "            else:\n",
    "                i+=1\n",
    "                \n",
    "        return  len(preorderList) == 1 and preorderList[0] == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        edge = 1\n",
    "\n",
    "        for node in preorder.split(','):\n",
    "            if node == '#':\n",
    "                edge -= 1\n",
    "                if edge < 0: return False \n",
    "            else:\n",
    "                edge -= 1\n",
    "                if edge < 0: return False \n",
    "                edge += 2\n",
    "\n",
    "        return edge == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidSerialization(self, preorder): ### 一个‘#’代表一个空！\n",
    "\n",
    "        stack=[]\n",
    "        for root in preorder.split(\",\"):\n",
    "            stack.append(root)\n",
    "            while len(stack)>=3 and stack[-2]==\"#\" and stack[-1]==\"#\" and stack[-3] != '#':\n",
    "                stack.pop(),stack.pop(),stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'\n",
    "\n",
    "        # stack=[]\n",
    "        # for root in preorder.split(','):\n",
    "        #     stack.append(root)\n",
    "        #     print(stack)\n",
    "        #     while len(stack)>=3 and stack[-1]==stack[-2]=='#' and stack[-3] != '#': ### 这里绝对不能用if，\n",
    "        #     ## 比如消掉4，1 以后，应该再次消掉新生成的3\n",
    "        #         stack.pop(),stack.pop(),stack.pop()\n",
    "        #         stack.append('#')\n",
    "        # return len(stack) == 1 and stack.pop() == '#'\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # stack = []\n",
    "        # for node in preorder.split(','):\n",
    "        #     stack.append(node)\n",
    "        #     while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#': ### 找到一个椰子树节点了\n",
    "        #         stack.pop(), stack.pop(), stack.pop() ### 全都pop出去\n",
    "        #         stack.append('#') ### 加入一个标记\n",
    "        # return len(stack) == 1 and stack.pop() == '#'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        node_list = preorder.split(',')\n",
    "        i = len(node_list) - 2\n",
    "        while i > 0:\n",
    "            if node_list[i] == node_list[i + 1] == '#' and node_list[i - 1] != '#':\n",
    "                node_list.pop()\n",
    "                node_list.pop()\n",
    "                node_list[i - 1] = '#'\n",
    "                i = len(node_list) - 2\n",
    "            else:\n",
    "                i -= 1\n",
    "        return node_list == ['#']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def isValidSerialization(self, preorder: str) -> bool:\n",
    "    #     #图论解法\n",
    "    #     in_degree = 0\n",
    "    #     out_degree = 0\n",
    "    #     pre_list = preorder.split(',')\n",
    "    #     nodes_count = len(pre_list)\n",
    "    #     for i, ch in enumerate(pre_list):\n",
    "    #         if i != 0:\n",
    "    #             in_degree += 1\n",
    "    #         if ch != '#':\n",
    "    #             out_degree += 2\n",
    "    #         if i != nodes_count-1 and out_degree <= in_degree:\n",
    "    #             return False\n",
    "    #     return in_degree == out_degree\n",
    "    # def isValidSerialization(self, preorder: str) -> bool:\n",
    "    #     #辅助栈合成大西瓜\n",
    "    #     pre_stack = []\n",
    "    #     pre_list = preorder.split(',')\n",
    "    #     for c in pre_list:\n",
    "    #         pre_stack.append(c)\n",
    "    #         while len(pre_stack) >= 3 and pre_stack[-1] == '#' and pre_stack[-2] == '#' and pre_stack[-3] != '#':\n",
    "    #             pre_stack.pop()\n",
    "    #             pre_stack.pop()\n",
    "    #             pre_stack.pop()\n",
    "    #             pre_stack.append('#')\n",
    "    #     return len(pre_stack) == 1 and pre_stack[-1] == '#'\n",
    "\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        pre_stack = []\n",
    "        pre_list = preorder.split(',')\n",
    "        for c in pre_list:\n",
    "            if c != '#':\n",
    "                pre_stack.append(c)\n",
    "            else:\n",
    "                while len(pre_stack) >= 2 and pre_stack[-1] == '#' and pre_stack[-2] != '#':\n",
    "                    pre_stack.pop()\n",
    "                    pre_stack.pop()\n",
    "                pre_stack.append('#')\n",
    "        return len(pre_stack) == 1 and pre_stack[-1] == '#'\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None \n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        \n",
    "        preorder = preorder.split(',')\n",
    "\n",
    "        def build():\n",
    "            nonlocal preorder\n",
    "            if preorder[0] == '#':\n",
    "                preorder = preorder[1:]\n",
    "                return None \n",
    "            root = Tree(preorder[0])\n",
    "            preorder = preorder[1:]\n",
    "            root.left = build()\n",
    "            root.right = build()\n",
    "        \n",
    "        try:\n",
    "            build()\n",
    "            return len(preorder) == 0\n",
    "        except Exception as e:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        for node in preorder.split(','):\n",
    "            stack.append(node)\n",
    "            while len(stack) >= 3 and stack[-1] == '#' and stack[-2] == '#' and stack[-3] != '#':\n",
    "                stack.pop(-1)\n",
    "                stack.pop(-1)\n",
    "                stack[-1] = '#'\n",
    "        return len(stack) == 1 and stack[0] == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\r\n",
    "        #遇到两个#回退一个数字变成# -> 节点下无子节点然后被删除\r\n",
    "        stack = []\r\n",
    "        for i in preorder.split(','):\r\n",
    "            stack.append(i)\r\n",
    "            while len(stack) >= 3 and stack[-1] == '#' and stack[-2] == '#' and stack[-3] != '#':\r\n",
    "                stack.pop()\r\n",
    "                stack.pop()\r\n",
    "                stack.pop()\r\n",
    "                stack.append('#')\r\n",
    "        return len(stack) == 1 and stack[0] == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        for node in preorder.split(','):\n",
    "            stack.append(node)\n",
    "            while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        for node in preorder.split(\",\"):\n",
    "            stack.append(node)\n",
    "            while len(stack) >= 3 and stack[-1] == stack[-2] == \"#\" and stack[-3] != \"#\":\n",
    "                for _ in range(3):\n",
    "                    stack.pop()\n",
    "        #         stack.append(\"#\")\n",
    "        #     return len(stack) == 1 and stack.pop() == \"#\"\n",
    "\n",
    "\n",
    "        # for node in preorder.split(','):\n",
    "            # stack.append(node)\n",
    "            # while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#':\n",
    "                # stack.pop(), stack.pop(), stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\r\n",
    "        #遇到两个#回退一个数字变成#\r\n",
    "        stack = []\r\n",
    "        for i in preorder.split(','):\r\n",
    "            stack.append(i)\r\n",
    "            while len(stack) >= 3 and stack[-1] == '#' and stack[-2] == '#' and stack[-3] != '#':\r\n",
    "                stack.pop()\r\n",
    "                stack.pop()\r\n",
    "                stack.pop()\r\n",
    "                stack.append('#')\r\n",
    "        return len(stack) == 1 and stack[0] == '#'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        stack = []\n",
    "        s=preorder.split(\",\")\n",
    "\n",
    "        for i in s:\n",
    "            stack.append(i)\n",
    "            while len(stack)>2 and stack[-1] == '#' and stack[-2] == '#' and stack[-3].isdigit():\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append(\"#\")\n",
    "        return len(stack)==1 and stack[0]=='#'\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        d = list(preorder.split(','))\n",
    "        stack = []\n",
    "        for i in d:\n",
    "            stack.append(i)\n",
    "            while len(stack)>2 and stack[-1] == stack[-2] =='#' and stack[-3]!='#':\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.pop()\n",
    "                stack.append('#')\n",
    "            \n",
    "                \n",
    "        print(stack)\n",
    "        return stack == ['#']\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isValidSerialization(self, preorder: str) -> bool:\n",
    "        if len(preorder) == 0:\n",
    "            return False\n",
    "        preorder = preorder.split(',')\n",
    "        stack = [1]\n",
    "        for data in preorder:\n",
    "            if len(stack) == 0:\n",
    "                return False\n",
    "            stack[-1] -= 1 # 只要来了一个元素，一定会占了栈顶的一个位置\n",
    "            if stack[-1] == 0:\n",
    "                stack.pop()\n",
    "            if data != '#':\n",
    "                stack.append(2)\n",
    "            # else:\n",
    "            #     stack[-1] -= 1\n",
    "        return len(stack) == 0\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isValidSerialization(self, preorder): ### 一个‘#’代表一个空！\n",
    "        stack=[]\n",
    "        for root in preorder.split(','):\n",
    "            stack.append(root)\n",
    "            print(stack)\n",
    "            while len(stack)>=3 and stack[-1]==stack[-2]=='#' and stack[-3] != '#': ### 这里绝对不能用if，\n",
    "            ## 比如消掉4，1 以后，应该再次消掉新生成的3\n",
    "                stack.pop(),stack.pop(),stack.pop()\n",
    "                stack.append('#')\n",
    "        return len(stack) == 1 and stack.pop() == '#'\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # stack = []\n",
    "        # for node in preorder.split(','):\n",
    "        #     stack.append(node)\n",
    "        #     while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#': ### 找到一个椰子树节点了\n",
    "        #         stack.pop(), stack.pop(), stack.pop() ### 全都pop出去\n",
    "        #         stack.append('#') ### 加入一个标记\n",
    "        # return len(stack) == 1 and stack.pop() == '#'\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
